package com.hy;

import java.util.PriorityQueue;

/**
 * Created With IntelliJ IDEA.
 * Descriptions:合并 K 个升序链表
 *
 * 给定一个链表数组，每个链表都已经按升序排列。
 * 请将所有链表合并到一个升序链表中，返回合并后的链表。
 *
 * author: Mr.Du
 * Date: 2023/11/15
 * Time: 17:23
 */
public class MergeKLists {
    /**
     * 使用PriorityQueue队列，进行操作，
     * PriorityQueue：它的底层是一个队列，但是队列满足最小堆
     * @param lists
     * @return
     */
    public ListNode mergeKLists(ListNode[] lists) {
        if(lists.length == 0) return null;
        PriorityQueue<ListNode> pq = new PriorityQueue<>(
                lists.length, (a, b)->(a.val - b.val));
        ListNode dummy = new ListNode(-1);
        ListNode cur = dummy;
        for(ListNode node : lists){
            if(node != null)  pq.offer(node);
        }
        while(pq.size() > 0){
            ListNode head = pq.poll();
            if(head != null && head.next != null){
                pq.offer(head.next);
            }
            cur.next = head;
            cur = head;
        }
        return dummy.next;
    }
}
